K largest elements in an Array

Method 1 - Use Sorting

Time complexity: O(N * logN)

  1. Sort the elements in descending order in O(NLogN)

  2. Print the first k numbers of the sorted array O(k).

def k_largest(A, k):
    # Sort the given array arr in reverse order.
    A.sort(reverse = True)
    # Print the first k-th largest elements
    for i in range(k):
        print(A[i], end=" ")
    # Driver program

array = [1, 23, 12, 9, 30, 2, 50]    # [1, 2, 9, 12, 23, 30, 50]
# n = len(arr)
k = 3
k_largest(array, k)

Method 2 - Use Bubble k times

Time Complexity: O(Nk)

  1. Modify Bubble Sort to run the outer loop at most k times.

  2. Print the last k elements of the array obtained in step 1.

Like Bubble sort, other sorting algorithms like Selection Sort can also be modified to get the k largest elements.

Method 3 - Use temporary array

Time Complexity: O((N-k)*k).

K largest elements from arr[0..n-1]:

  1. Store the first k elements in a temporary array temp[0..k-1].

  2. Find the smallest element in temp[], let the smallest element be min.

  3. For each element x in arr[k] to arr[n-1]. If x is greater than the min then remove min from temp[] and insert x.

  4. Print final k elements of temp[]

If we want the output sorted then O((n-k)*k + klogk)

Method 4 - Use Max Heap

Time complexity: O(n + k*logN)

  1. Build a Max Heap tree in O(n)

  2. Use Extract Max k times to get k maximum elements from the Max Heap - O(k* logn)

Method 5 - Use Oder Statistics

Time complexity: O(n)

  1. Use order statistic algorithm to find the kth largest element. Please see the topic selection in worst-case linear time O(n)

  2. Use QuickSort Partition algorithm to partition around the kth largest number O(n).

  3. Sort the k-1 elements (elements greater than the kth largest element) O(kLogk). This step is needed only if sorted output is required. if we don’t need the sorted output, otherwise O(n+kLogk)